Link to this headingECC

Elliptic Curve Cryptography Math Introduction
Elliptic Curve Cryptography Math Introduction with examples
Elliptic Curve Cryptography with Graphs and code
The Animated Elliptic Curve

Security:

  • Needs Good RNGs
  • Bad Curves

Definitions:

  • g is a generator point. Depending on the Curve this can be any point or a specific subset of points
  • n is the order. This is how many Points exist in the generator point before repeating. Aka P*n = infinity point

Link to this headingProperties of a Elliptic Curve

Elliptic Curve Cryptography uses a collection of X,Y coordinates where x and y range is from [0,p].
This plain is symmetrical across the x axis

Because of this modulus of p where it is a prime number the x,y plane is associative and commutative.

Example Elliptic Curve Formula:

y^2 = x^3 + ax + b \pmod{P}

Multiplying by a integer converts it into a trapdoor function.


Given a point P and a number n, computing a point Q such that Q = n * P is very easy.

Given a point P and a point Q, finding n such that Q = n * P is extremely hard.


Link to this headingAdding Mod


Like always we use a mod of a prime number to make sure that there is not a message that is divisible by the modulus.


When adding the mod a property shows its self. For some integer n there exists the congruency nP = 0. This also means that (n + 1)P = P


Link to this headingAddition on an Elliptic Curve


Source


Take an origin point P and a travel point Q. With a line going from point P to point Q there is either 1 point or no points. If the point exists than lets call that point R.


There exists a point -R which is just reflected over the X axis. This is also on the curve since the curve is symmetrical over the X axis.


Find Slope Example:


P + Q = R
(x_p, y_p) + (x_q, y_q) = (x_r, y_r)

slope = \dfrac{y_q - y_p}{x_q - x_p}

Find Point on Curve:


x_r = slope^2 - x_q - x_p
y_r = -( y_q + slope * ( x_r - x_q))

Point Addition:


	def add_point(self, point1, point2):
		#Check if both points are on the curve
		if (not self.is_on_curve(point1)) or (not self.is_on_curve(point2)):
			raise ValueError("The points are not on the curve.")

		#Check if either are infinity points
		if point1.isInifinityPoint():
			return point2
		elif point2.isInifinityPoint():
			return point1

		#Check for other relation properties
		if point1 == point2:
			#Double Point because needs specific slope calculation
			return self._double_point(point1)
		if point1 == -point2:
			#Return Infinity point
			return Point(None, None, self)

		#Do Curve specific Point Addition
		return self._add_point(point1, point2)

	def double_point(self, point):
		if not self.is_on_curve(point):
			raise ValueError("The point is not on the curve.")
		if point.isInifinityPoint():
			#Return Infinity point
			return Point(None, None, self)

		#Do Curve Specific Point Addition
		return self._double_point(point)



	def _add_point(self, point1, point2):
		# Compute the slope using y2-y1/x2-x1. Using a mod inverse instead of division
		slope = (point2.y - point1.y) * modinv(point2.x - point1.x, self.prime_mod)

		#Compute the new X point
		# y = mx + d
		# d = y_1 - m(x_1)

		# y^2 = x^3 + a*x + b
		# b = (y_1)^2 - (x_1)^3 + x(x_1)

		# y^2 = (mx + d)^2 
		#     = m^2x^2 + 2mxd + d^2 
		#     = m^2x^2 + 2mx(y_1 - m(x_1)) + (y_1 - m(x_1))^2
		#     = x^2(m^2) + 2x(m(y_1) - (m^2)(x_1)) + (y_1)^2 - 2m(x_1)(y_1) + m^2(x_1)^2

		# Set the functions equal to each other and solve for zero
		# x^2(m^2) + 2x(m(y_1) - (m^2)(x_1)) + (y_1)^2 - 2m(x_1)(y_1) + m^2(x_1)^2 = x^3 + a*x + b
		# x^2(m^2) + 2x(m(y_1) - (m^2)(x_1)) + (y_1)^2 - 2m(x_1)(y_1) + m^2(x_1)^2 -x^3 - a*x - b = 0
		# x^3 - x^2(m^2) - 2x(m(y_1) + (m^2)(x_1)) - (y_1)^2 + 2m(x_1)(y_1) - m^2(x_1)^2 + a*x + b = 0

		#We know the roots of the equation (x - x_1)(x - x_2)(x - x_3)
		#Lets set them equal to each other
		# x^3 - x^2(m^2) - 2x(m(y_1) + (m^2)(x_1)) - (y_1)^2 + 2m(x_1)(y_1) - m^2(x_1)^2 + a*x + b = (x - x_1)(x - x_2)(x - x_3)
		# x^3 - x^2(m^2) - 2x(m(y_1) + (m^2)(x_1)) - (y_1)^2 + 2m(x_1)(y_1) - m^2(x_1)^2 + a*x + b = x^3 -x^2((x_3) + (x_2) + (x_1)) + x((x_1)(x_2) + (x_1)(x_3) + (x_2)(x_3)) - (x_1)(x_2)(x_3)

		# That means that -x^2(m^2) = -x^2((x_3) + (x_2) + (x_1))
		# (m^2) = ((x_3) + (x_2) + (x_1))
		# x_3 = (m^2) - (x_2) - (x_1)

		# x = m^2 -x_1 -x_2
		result_x = (slope**2 - point1.x - point2.x) % self.prime_mod

		#Once we know x its easy to find y
		# y = mx + d
		# d = y_1 - m(x_1)
		# y = mx + y_1 - m(x_1)
		# y_3 = m(x_3) + y_1 - m(x_1)
		# y_3 = m((x_3) - (x_1)) + y_1

		#We take the negative since we want -R which is reflected over the x axis
		result_y = (-(slope * (result_x - point1.x) + point1.y)) % self.prime_mod
		return Point(point_x=result_x, point_y=result_y, curve=self)


	def _double_point(self, point1):
		#Find the tangent of the line at the point
		#This is done by taking the dirivitive of the Cure formula y^2 = x^3 + a*x + b (mod p)
		# 2y = 3x^2 + a 
		slope = (3 * point1.x**2 + self.a) * modinv(2 * point1.y, self.prime_mod)

		#Compute the new X point
		# y = mx + d
		# d = y_1 - m(x_1)

		# y^2 = x^3 + a*x + b
		# b = (y_1)^2 - (x_1)^3 + x(x_1)

		# y^2 = (mx + d)^2 
		#     = m^2x^2 + 2mxd + d^2 
		#     = m^2x^2 + 2mx(y_1 - m(x_1)) + (y_1 - m(x_1))^2
		#     = x^2(m^2) + 2x(m(y_1) - (m^2)(x_1)) + (y_1)^2 - 2m(x_1)(y_1) + m^2(x_1)^2

		# Set the functions equal to each other and solve for zero
		# x^2(m^2) + 2x(m(y_1) - (m^2)(x_1)) + (y_1)^2 - 2m(x_1)(y_1) + m^2(x_1)^2 = x^3 + a*x + b
		# x^2(m^2) + 2x(m(y_1) - (m^2)(x_1)) + (y_1)^2 - 2m(x_1)(y_1) + m^2(x_1)^2 -x^3 - a*x - b = 0
		# x^3 - x^2(m^2) - 2x(m(y_1) + (m^2)(x_1)) - (y_1)^2 + 2m(x_1)(y_1) - m^2(x_1)^2 + a*x + b = 0


		#We know the roots of the equation (x - x_1)(x - x_2)(x - x_3)
		#Lets set them equal to each other
		# x^3 - x^2(m^2) - 2x(m(y_1) + (m^2)(x_1)) - (y_1)^2 + 2m(x_1)(y_1) - m^2(x_1)^2 + a*x + b = (x - x_1)(x - x_1)(x - x_3)
		# x^3 - x^2(m^2) - 2x(m(y_1) + (m^2)(x_1)) - (y_1)^2 + 2m(x_1)(y_1) - m^2(x_1)^2 + a*x + b = + x^3 - x^2(2(x_1) + (x_3)) + x(x_1)^2 + 2x(x_1)(x_3)  -(x_1)^2(x_3)

		# That means that - x^2(m^2) = - x^2(2(x_1) + (x_3))
		# m^2 = 2(x_1) + (x_3)
		# m^2 - 2(x_1) = (x_3)

		# Compute the new point. This is the same info from the add point
		# Since there is no second point it is just 2* the same point
		result_x = (slope**2 - (2 * point1.x)) % self.prime_mod

		# y   = m*(x - x_1) + y_1
		# y_3 = m*(x_3 - x_1) + y_1

		#We take the negative since we want -R which is reflected over the x axis
		result_y = (-(slope * (result_x - point1.x) + point1.y)) % self.prime_mod
		return Point(point_x=result_x, point_y=result_y, curve=self)

Link to this headingMultiplications on an Elliptic Curve


Addition is just multiple additions. Similar to the Square and Multiply for bits in a [RSA](/Crypto/Asymmetric Encryption/RSA) key the same thing can be done here.


#R = k * P

	def mul_point(self, scalar, point):
		#Check if Point is on Curve
		if not self.is_on_curve(point):
			raise ValueError("The point is not on the curve.")

		#Check if point Provided is Infinity
		if point.isInifinityPoint():
			#Return Infinity point
			return Point(None, None, self)

		#Check if multiplied by Zero
		if scalar == 0:
			#Return Infinity point
			return Point(None, None, self)

		#Check if Scalar is negative
		if scalar < 0:
			# Split the negative Multiplication into -1 * scalar
			# This allows the regular operations then taking the negative of the resulting point
			temp_scalar = -scalar
		else:
			temp_scalar = scalar


		#Initialize result to the Infinity point
		result = Point(None, None, self)
		temp_point = point

		while temp_scalar:
			#Check if current least significant bit is set
			# If set then add the initial point to the running total
			if temp_scalar & 0x1 == 1:
				result = temp_point + result

			#Increase the Point by 2 to be used if the bit is set
			temp_point = self.double_point(temp_point)

			#Decrease the scalor by 2 to check the next least significant
			temp_scalar >>= 1

		#Check if the scalar was negitive and invert the result
		if scalar < 0:
			return -result
		else:
			return result

Link to this headingOrder of Elliptic Curve


The Order of a Curve is the max number of valid points on the curve. This includes the infinity point.


    

  • This is calculated by finding the size of all of the subgroups.
    • 



Subgroups are non-overlaping sets of possible results that a point can be.


    

  • A sub-group could be all of the possible results that n * point1 could be.
    • 



Calculating and Order with Sage Math:


from sage.all import *
E = EllipticCurve(GF(310717010502520989590157367261876774703), [2, 3])
generator_point = E(179210853392303317793440285562762725654, 105268671499942631758568591033409611165)
print(f"Order: {E.order()}") # 310717010502520989590206149059164677804

#Check to see if the order is easily factorable
order_factors = factor(E.order())
print(order_factors) # 2^2 * 3^7 * 139 * 165229 * 31850531 * 270778799 * 179317983307


Link to this headingCofactor of an Elliptic Curve


Cofactors are the number of subgroups that a curve contains. This is the factors of the order of the curve


Link to this headingGenerator point


Generating the Generator Point:


from sage.all import *

def generator_point(E):
	order_coprime = [p for p, _ in E.order().factor()]
	for test_x in range(1, 100):

		test_points = E.lift_x(Integer(test_x), all=True)

		#Check if it has two points
		if len(test_points) == 2:
			pointOrder = test_points[0].order()

			print(test_points, pointOrder)

			#Check if order matches constraints
			# Is a prime number and is equal to the greatest prime from the curve order
			# aka in the large prime-order sub-group
			if pointOrder > 8 and pointOrder.is_prime() and pointOrder == order_coprime[-1]:
				return test_x, test_points[0], pointOrder.factor()
	

E = EllipticCurve(GF(pow(2,255) - 19), [0, 486662, 0, 1, 0])
print(f"Curve Order: {E.order()}")
print(f"Order Factors: {E.order().factor()}")
#Curve Order: 57896044618658097711785492504343953926856930875039260848015607506283634007912
#Order Factors: 2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989

g = generator_point(E)
print(g)
"""
[(1 : 9094040566125962849133224048217411091405536248825867518642941381412595940312 : 1), (1 : 48802004052532134862652268456126542835229456083994414501085850622543968879637 : 1)] 4
[(4 : 10396089888167458996693606908380331970145732977558722329349539962582616845133 : 1), (4 : 47499954730490638715091885595963621956489259355261559690379252041373947974816 : 1)] 28948022309329048855892746252171976963428465437519630424007803753141817003956
[(6 : 24305686323100213963426648412256631801221636864960734090508095036257779400554 : 1), (6 : 33590358295557883748358844092087322125413355467859547929220696967698785419395 : 1)] 57896044618658097711785492504343953926856930875039260848015607506283634007912
[(7 : 22162570367908009971983332230403424946970232071349602096662526808647397026575 : 1), (7 : 35733474250750087739802160273940528979664760261470679923066265195309167793374 : 1)] 57896044618658097711785492504343953926856930875039260848015607506283634007912
[(8 : 20738790057349198289249091238452691228459490893327641026453294524045724516251 : 1), (8 : 37157254561308899422536401265891262698175501439492640993275497479910840303698 : 1)] 57896044618658097711785492504343953926856930875039260848015607506283634007912
[(9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1), (9 : 43114425171068552920764898935933967039370386198203806730763910166200978582548 : 1)] 7237005577332262213973186563042994240857116359379907606001950938285454250989
(9, (9 : 14781619447589544791020593568409986887264606134616475288964881837755586237401 : 1), 7237005577332262213973186563042994240857116359379907606001950938285454250989)
"""

Link to this headingExample


[secp256k1](/Crypto/Asymmetric Encryption/Curves/Short Weierstrass Curves.md#secp256k1) Curve


Link to this headingInvalid Curve Point Attack


https://iacr.org/archive/pkc2003/25670211/25670211.pdf

https://blog.trailofbits.com/2018/08/01/bluetooth-invalid-curve-points/


Since a user chooses a point which contains both an x and y value the attacker can use any value for this.


Point on the Curve Checklist:


    

  • The x and y values are smaller than the modulus
    • 

  • The x and y values are using the curve formula are valid
    • 

  • The Point is not an Infinity point
    • 

  • The Point is in the correct subgroup
    • 



Link to this headingValues bigger than the Modulus


These values may mess with the Code. For some program languages like C there might be a maximum value for the integer. Going over that value might create invalid results


Example:


#24 * G = (115090238283566018960826468250608273126387416636633736439689841211757211870926, 47185183227829754668635270747409548752084785367264057948864458978444304762303)
	G24 = Point(curve=secp256k1, point_x=115090238283566018960826468250608273126387416636633736439689841211757211870926 + 10*secp256k1.prime_mod, point_y=47185183227829754668635270747409548752084785367264057948864458978444304762303+ 10000*secp256k1.prime_mod)
	print(secp256k1.is_on_curve(G24))
	#True
	print(G24)
	#secp256k1: 
	#x=1273011130656727973196536318337487351659087263293039376834265681290845558587556, 
	#y=1157968077556389783990378485357626488081451931441772904452524704538066791021392303

Link to this headingPoint is not on Curve


If a point is from an easier curve to attack and the point is not checked. This might lead to leaking the secret Key or making the encrypted data able to be decrypted without a private key.


Example:


	#### Point is not on Curve
	invalid_point = Point(curve=secp256k1, point_x=secp256k1_Generator_Point.x, point_y=G24.y)
	print(secp256k1.is_on_curve(invalid_point))
	#False
	print(invalid_point)
	#secp256k1: x=55066263022277343669578718895168534326250603453777594175500187360389116729240, y=1157968077556389783990378485357626488081451931441772904452524704538066791021392303

Link to this headingPoint is not an Infinity Point


If an infinity point is used then the


https://vnhacker.blogspot.com/2015/09/why-not-validating-curve25519-public.html